package com.linzm.leetcode.primary.exercises1_20230114;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author zimingl
 * @Date 2023/1/15 1:42
 * @Description: 在长度 2N 的数组中找出重复 N 次的元素
 */
public class Demo11_961 {
    public static void main(String[] args) {
        int [] nums = new int[] {1,2,3,3};
        Demo11_961 demo11_961 = new Demo11_961();
        int i = demo11_961.repeatedNTimes2(nums);
        System.out.println(i);
    }

    private int repeatedNTimes(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(10);
        for (int i = 0; i < nums.length; i++) {
            int count = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], count);
        }
        for (Map.Entry entry : map.entrySet()) {
            if (nums.length/2 == (int) entry.getValue()) {
                return (int) entry.getKey();
            }
        }
        return -1;
    }

    private int repeatedNTimes2(int[] nums) {
        Set<Integer> found = new HashSet<Integer>();
        for (int num : nums) {
            if (!found.add(num)) {
                return num;
            }
        }
        // 不可能的情况
        return -1;
    }
}
